//https://leetcode.cn/problems/reverse-linked-list/
//反转链表
//法一
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* doReverse(struct ListNode* head,struct ListNode** outhead){
    if(head==NULL || head->next==NULL){
        *outhead=head;
        return head;
    }
    struct ListNode* tail=doReverse(head->next,outhead);
    tail->next=head;
    head->next=NULL;
    return head;
}

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* outhead;
    doReverse(head,&outhead);
    return outhead;
}


//法二
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* doReverse(struct ListNode* head,struct ListNode** outhead){
    if(head==NULL||head->next==NULL){
        return head;
    }
    struct ListNode*n1=NULL,*n2=head,*n3=head->next;
    while(n2){
        n2->next=n1;

        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}